RedPwn Dimensionality Write Up

Details:

Jeopardy style CTF

Category: Reverse Engineering

Write up:

Looking into the main function I saw:

__int64 __fastcall main(int a1, char **a2, char **a3)
{
  int v3;
  int v4; 
  _BYTE *v5;
  char v6; 
  int v7; 
  __int8 v8;
  __int64 result; 
  __m128i v10; 
  char v11;
  unsigned __int8 v12; 
  char input[40];
  unsigned __int64 v14; 

  v14 = __readfsqword(0x28u);

  fgets(input, 29, stdin);                      // Read in data, with a length of 29
  if ( checkInputFunction(input, 29LL, v3) )    // check function
  {
    puts(":)");
    createCharMatrix(&v10, (__int64)input, 28uLL);
    v4 = v12;                                   // set v4 to 0
    v5 = &flag;                                 // set v5 to the address of the flag (points at first char)
    v6 = v11 + 1 - (unsigned __int8)&flag;      // sets v6 to 0xA1 (161)
    do
    {
      v7 = v10.m128i_u8[(unsigned __int8)(v6 + (_BYTE)v5)];// gets the value from the matrix
                                                // uses 0xA1 and the current character
      v4 += v7;                                 // adds the number we just got to v4
      v8 = v10.m128i_i8[(unsigned __int8)v4];   // using v4 look up the value for v8
      v10.m128i_i8[(unsigned __int8)(v6 + (_BYTE)v5)] = v8;// sets the value at the first look up index to the value of the second look up
      v10.m128i_i8[(unsigned __int8)v4] = v7;   // sets the value of the second lookup to the first lookup
      *v5++ ^= v10.m128i_u8[(unsigned __int8)(v8 + v7)];// xors the flags current value with the value at index v7+v8, then increments the flag pointer
    }
    while ( (char *)&flag + 41 != v5 );         // for the length of the flag
    fwrite(&flag, 1uLL, 41uLL, stdout);         // writes the flag, length of 41
    putc('\n', stdout);                         // print new line
    result = 0LL;                               // set result to 0
  }
  else                                          // not the right flag
  {
    puts(":(");
    result = 1LL;                               // set result to 1
  }
  return result;
}

I then saw that the checkInputFunction (which I renamed to this) was the following:

bool __fastcall checkInputFunction(char *inputString, __int64 a2, int a3)
{
  int v3; 
  __int64 v4;
  int v5; 
  char v6;
  char *v7; 
  int v8; 
  bool result;
  char v10;

  v3 = dword_55B4ED0E508C * dword_55B4ED0E508C * dword_55B4ED0E508C;// dword_564ED4C3608C seems to always be 0Bh (will be 0x533)
  if ( v3 > 0 )                                 // this should always be hit since 0x0B*0x0B*0x0B will always be greater than 0
  {
    v4 = 1LL;
    while ( 1 )
    {
      v5 = v4;
      if ( v3 == v4 )
        break;
      if ( *((_BYTE *)&unk_55B4ED0E307F + ++v4) == 2 )
      {
        a3 = v5;
        break;
      }
    }
  }
  v6 = *inputString;                            // set v6 to the first character of the input string
  v7 = inputString + 1;                         // set to the input minus the first character
  v8 = dword_55B4ED0E508C * dword_55B4ED0E508C; // sets v8 to 121 (11*11)
  if ( *inputString )
  {
    while ( 1 )                                 // current character in input string
    {
      switch ( v6 )
      {
        case 'b':                               // if character is b
          v8 = -(dword_55B4ED0E508C * dword_55B4ED0E508C);// set v8 to -121
          break;
        case 'd':                               // if character is d
          v8 = dword_55B4ED0E508C;              // st v8 to 11
          break;
        case 'f':                               // if character is f
          v8 = dword_55B4ED0E508C * dword_55B4ED0E508C;// set v8 to 121
          break;
        case 'l':                               // if character is l
          v8 = -1;                              // set v8 to -1
          break;
        case 'r':                               // if character is r
          v8 = 1;                               // set v8 to 1
          break;
        case 'u':                               // if character is u
          v8 = -dword_55B4ED0E508C;             // set v8 to -11
          break;
        default:                                // if character is none of the above
          break;
      }
      a3 += v8;                                 // adds the value of v8 to a3 (a3 starts at 0)
      result = a3 < 0 || a3 > v3;               // if a3 is less than 0 or greater than 1331 set to true
      if ( result )                             // if true then exit the loop and sets return to false
        break;
      v10 = byte_55B4ED0E3080[a3];              // use a3 to look up an array and set v10 to that value
      if ( !v10 )                               // if v10 is false (0) then return the last result (will be false), need to make sure not to hit this
        return result;
      v6 = *v7++;                               // increment v6 to the next character
      if ( !v6 )                                // if v6 is no longer a character jump to the end and see if v10 is 3
        goto LABEL_12;
    }
    result = 0;
  }
  else
  {
    v10 = byte_55B4ED0E3080[a3];                // get v10 from the array again
LABEL_12:
    result = v10 == 3;                          // set result to whether v10 equals 3
  }
  return result;
}

After commenting the two functions I started getting to work. The first thing I did was extract the byte_55B4ED0E3080 array.

This array was used for making the "path" to the final check where the value in the array was 3 when the index was the sum of the characters.

From this we extracted an array of all the indices that we could access (any that were not 0):

v10Arr = [0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x01, 0x01, 0x01, 0x00, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x01, 0x00, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x01, 0x01, 0x00, 0x01, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00, 0x01, 0x01, 0x01, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00, 0x01, 0x01, 0x01, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x01, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x01, 0x00, 0x01, 0x01, 0x01, 0x00, 0x01, 0x01, 0x01, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x01, 0x00, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x01, 0x00, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x01, 0x00, 0x01, 0x01, 0x01, 0x00, 0x01, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00]

newArr = []

for i in range(0, len(v10Arr)-1):
	if v10Arr[i] != 0:
		newArr.append(i)

print(newArr)

This printed out:

[84, 133, 134, 135, 136, 137, 141, 146, 152, 155, 156, 157, 159, 160, 161, 162, 163, 166, 168, 174, 177, 178, 179, 180, 181, 185, 188, 190, 192, 199, 200, 201, 203, 204, 205, 206, 207, 210, 212, 214, 216, 221, 223, 224, 225, 226, 227, 254, 262, 276, 278, 282, 320, 322, 328, 344, 375, 377, 379, 380, 381, 383, 386, 388, 392, 397, 398, 399, 400, 401, 403, 404, 405, 408, 410, 414, 419, 421, 423, 424, 425, 432, 434, 441, 442, 443, 444, 445, 446, 447, 448, 449, 452, 454, 463, 464, 465, 466, 467, 469, 496, 498, 502, 518, 520, 524, 540, 542, 546, 562, 564, 566, 568, 586, 588, 590, 617, 619, 621, 622, 623, 628, 630, 632, 639, 640, 641, 642, 643, 645, 646, 647, 650, 652, 658, 661, 663, 667, 669, 683, 685, 686, 687, 688, 689, 694, 698, 700, 705, 707, 709, 710, 711, 712, 713, 738, 742, 760, 764, 782, 804, 806, 826, 830, 859, 860, 861, 862, 863, 864, 865, 866, 867, 870, 872, 874, 881, 883, 885, 886, 887, 889, 894, 896, 898, 900, 903, 904, 905, 906, 907, 909, 911, 914, 918, 920, 922, 925, 927, 928, 929, 931, 932, 933, 936, 938, 940, 944, 947, 949, 950, 951, 952, 953, 955, 982, 1002, 1006, 1028, 1052, 1054, 1068, 1074, 1103, 1114, 1123, 1124, 1125, 1127, 1128, 1129, 1149, 1150, 1151, 1167, 1168, 1169, 1171, 1172, 1173, 1175, 1178, 1184, 1189, 1190, 1191, 1195, 1296]

One of my teammates (Polymero) and I then made a script to print out all the possible paths that would pass the check since there were multiple paths that fit the criteria and could produce a flag. From the main function we knew the input would need to be 28 characters long:

import random

# possible sums
possum = [84, 133, 134, 135, 136, 137, 141, 146, 152, 155, 156, 157, 159, 160, 161, 162, 163, 166, 168, 174, 177, 178, 179, 180, 181, 185, 188, 190, 192, 199, 200, 201, 203, 204, 205, 206, 207, 210, 212, 214, 216, 221, 223, 224, 225, 226, 227, 254, 262, 276, 278, 282, 320, 322, 328, 344, 375, 377, 379, 380, 381, 383, 386, 388, 392, 397, 398, 399, 400, 401, 403, 404, 405, 408, 410, 414, 419, 421, 423, 424, 425, 432, 434, 441, 442, 443, 444, 445, 446, 447, 448, 449, 452, 454, 463, 464, 465, 466, 467, 469, 496, 498, 502, 518, 520, 524, 540, 542, 546, 562, 564, 566, 568, 586, 588, 590, 617, 619, 621, 622, 623, 628, 630, 632, 639, 640, 641, 642, 643, 645, 646, 647, 650, 652, 658, 661, 663, 667, 669, 683, 685, 686, 687, 688, 689, 694, 698, 700, 705, 707, 709, 710, 711, 712, 713, 738, 742, 760, 764, 782, 804, 806, 826, 830, 859, 860, 861, 862, 863, 864, 865, 866, 867, 870, 872, 874, 881, 883, 885, 886, 887, 889, 894, 896, 898, 900, 903, 904, 905, 906, 907, 909, 911, 914, 918, 920, 922, 925, 927, 928, 929, 931, 932, 933, 936, 938, 940, 944, 947, 949, 950, 951, 952, 953, 955, 982, 1002, 1006, 1028, 1052, 1054, 1068, 1074, 1103, 1114, 1123, 1124, 1125, 1127, 1128, 1129, 1149, 1150, 1151, 1167, 1168, 1169, 1171, 1172, 1173, 1175, 1178, 1184, 1189, 1190, 1191, 1195, 1296]

start = 84
goal = 1296

# possible steps
def posstep(x):
    return [i for i in [x-1,x-11,x-121,x+1,x+11,x+121] if i in possum]
    
# walking function
def walk(length=None):
    
    WON = False
    dead_ends = 0
    starvations = 0
    
    while True:
        
        locat = [start]
        steps = []
        
        while True:
            
            posmoves = posstep(locat[-1])
            
            try:
                posmoves.remove(locat[-2])
            except:
                pass
            
            if not posmoves:
                dead_ends += 1
                break
            
            r_locat = random.choice(posmoves)
            
            steps += [r_locat - locat[-1]]
            locat += [r_locat]
            
            if len(steps) > 29:
                starvations += 1
                break
            
            if locat[-1] == goal:
                
                if length:
                    if len(steps) == length:
                        WON = True
                else:
                    WON = True
                    
                break
        
        if WON:
            break
    
    return steps

# translation dictionary (numbers to letters)
translate = { -121:'b', 11:'d', 121:'f', -1:'l', 1:'r', -11:'u'}

solutions = []

# walk the path 100 times
for k in range(100):
    
    sol = walk()
    wrd = ''.join([translate[i] for i in sol])
    
    if wrd not in solutions:
        solutions += [wrd]
        
# print all the found solutions
for s in solutions:
    print(s)

When run the script output:

frrffllffddllffrrffuubbrrfff
frrffllffllddffrrffuubbrrfff
fddllllffrrffffrrffuubbrrfff
frrffllllffddffrrffuubbrrfff
fllddllffrrffffrrffuubbrrfff

When tested against the binary we got that the correct input was:

frrffllffddllffrrffuubbrrfff

When put into the binary I got:

./chall

frrffllffddllffrrffuubbrrfff
:)
flag{star_/_so_bright_/_car_/_site_-ppsu}